Distinguisher-Dependent Simulation in Two Rounds and its Applications

Abhishek Jain; Yael Tauman Kalai; Dakshita Khurana; Ron Rothblum

Paper 2017/330

Distinguisher-Dependent Simulation in Two Rounds and its Applications

Abhishek Jain, Yael Tauman Kalai, Dakshita Khurana, and Ron Rothblum

Abstract

We devise a novel simulation technique that makes black-box use of the adversary as well as the distinguisher. Using this technique we construct several round-optimal protocols, many of which were previously unknown even using non-black-box simulation techniques: - Two-round witness indistinguishable (WI) arguments for $\NP$ from different assumptions than previously known. - Two-round arguments and three-round arguments of knowledge for that achieve strong WI, witness hiding (WH) and distributional weak zero knowledge (WZK) properties in a setting where the instance is only determined by the prover in the last round of the interaction. The soundness of these protocols is guaranteed against adaptive provers. - Three-round two-party computation satisfying input-indistinguishable security as well as a weaker notion of simulation security against malicious adversaries. - Three-round extractable commitments with guaranteed correctness of extraction from polynomial hardness assumptions. Our three-round protocols can be based on DDH or QR or N^th residuosity and our two-round protocols require quasi-polynomial hardness of the same assumptions. In particular, prior to this work, two-round WI arguments for NP were only known based on assumptions such as the existence of trapdoor permutations, hardness assumptions on bilinear maps, or the existence of program obfuscation; we give the first construction based on (quasi-polynomial) DDH. Our simulation technique bypasses known lower bounds on black-box simulation [Goldreich-Krawcyzk'96] by using the distinguisher's output in a meaningful way. We believe that this technique is likely to find more applications in the future.

Note: Three round protocols have been updated.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in CRYPTO 2017
Keywords: input-delayed weak zero knowledge strong witness indistinguishability witness hiding two rounds input indistinguishable computation
Contact author(s): dakshita @ cs ucla edu
History: 2017-12-01: last of 4 revisions; 2017-04-17: received; See all versions
Short URL: https://ia.cr/2017/330
License: CC BY

BibTeX

@misc{cryptoeprint:2017/330,
      author = {Abhishek Jain and Yael Tauman Kalai and Dakshita Khurana and Ron Rothblum},
      title = {Distinguisher-Dependent Simulation in Two Rounds and its Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/330},
      year = {2017},
      url = {https://eprint.iacr.org/2017/330}
}